package main

import (
	"container/list"
)

func pacificAtlantic(heights [][]int) [][]int {
	M := len(heights)
	N := len(heights[0])
	res := make([][]int, 0)
	v1 := bfs(heights, true)
	v2 := bfs(heights, false)
	for i := 0; i < M; i++ {
		for j := 0; j < N; j++ {
			if v1[i][j] && v2[i][j] {
				res = append(res, []int{i, j})
			}

		}
	}
	return res
}

func bfs(heights [][]int, pOrA bool) [][]bool {
	M := len(heights)
	N := len(heights[0])
	q := list.New()
	visited := new2dSlice(M, N)
	if pOrA {
		for i := 0; i < M; i++ {
			q.PushBack([]int{i, 0})
			visited[i][0] = true
		}
		for j := 1; j < N; j++ {
			q.PushBack([]int{0, j})
			visited[0][j] = true
		}
	} else {
		for i := 0; i < M; i++ {
			q.PushBack([]int{i, N - 1})
			visited[i][N-1] = true
		}
		for j := 0; j < N-1; j++ {
			q.PushBack([]int{M - 1, j})
			visited[M-1][j] = true
		}
	}
	dirs := [][]int{
		{-1, 0}, {1, 0}, {0, -1}, {0, 1},
	}
	for q.Len() > 0 {
		p := q.Remove(q.Front()).([]int)
		x := p[0]
		y := p[1]
		for _, dir := range dirs {
			x2 := x + dir[0]
			y2 := y + dir[1]
			if x2 >= 0 && x2 < M && y2 >= 0 && y2 < N &&
				!visited[x2][y2] && heights[x2][y2] >= heights[x][y] {
				q.PushBack([]int{x2, y2})
				visited[x2][y2] = true
			}
		}
	}
	return visited
}

func new2dSlice(M, N int) [][]bool {
	var arr [][]bool
	for i := 0; i < M; i++ {
		a := make([]bool, N)
		arr = append(arr, a)
	}
	return arr
}

func main() {

}
